int* path;
int pathTop;
int** ans;
int ansTop;
int* lengths; // step 0# 用于记录每个子集的长度

// step 1# 快速排序用的比较函数
int cmp(const void* a, const void* b) {
    return *((int*)a) - *((int*)b);
}

// step 2# 将当前 path 复制为一个子集，加入结果 ans 中，同时记录长度
void copy() {
    int* tempPath = (int*)malloc(sizeof(int) * pathTop);
    for(int i = 0; i < pathTop; i++) {
        tempPath[i] = path[i];
    }
    ans = (int**)realloc(ans, sizeof(int*) * (ansTop + 1));
    lengths[ansTop] = pathTop;
    ans[ansTop++] = tempPath;
}

// step 3# 回溯主函数
void backTracking(int* nums, int numsSize, int startIndex, int* used) {
    copy(); // step 3.1# 收集当前子集

    if(startIndex >= numsSize) return; // step 3.2# 终止条件

    // note 1### 跳过重复元素
    for(int i = startIndex; i < numsSize; i++) {
        // step 3.3# 跳过重复元素（去重的关键逻辑）
        if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)
            continue;

        // step 3.4# 选择当前元素
        path[pathTop++] = nums[i];
        used[i] = true;

        // step 3.5# 递归进入下一层
        backTracking(nums, numsSize, i + 1, used);

        // step 3.6# 回溯，撤销选择
        used[i] = false;
        pathTop--;
    }
}

// step 4# 主函数入口
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // step 4.1# 初始化辅助变量
    path = (int*)malloc(sizeof(int) * numsSize);
    ans = (int**)malloc(0);
    lengths = (int*)malloc(sizeof(int) * 1500);
    int* used = (int*)malloc(sizeof(int) * numsSize);
    pathTop = ansTop = 0;

    // note 2### 去重前要排序
    // step 4.2# 排序，为去重做准备
    qsort(nums, numsSize, sizeof(int), cmp);

    // step 4.3# 启动回溯
    backTracking(nums, numsSize, 0, used);

    // step 4.4# 设置返回值
    *returnSize = ansTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
    for(int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = lengths[i];
    }

    return ans;
}

/* 1. 20250424 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

/*
    去重逻辑解释：
    step 0# 输入先排序，使得相同元素相邻，便于后续去重判断
    step 1# 在回溯中使用 used 数组记录某个元素是否在当前路径中被使用过
    step 2# 如果当前元素 nums[i] 与前一个元素 nums[i-1] 相等，且前一个元素未使用（used[i-1] == 0）
           → 说明是在同一层尝试重复元素，应跳过
    step 3# 注意用于“去重”的 used 数组并不是子集最终选择标记，而是用于剪枝判断是否同层选过
*/

// step A# 全局变量定义
int **ans;       // 存储结果集（二维数组）
int *ansLen;     // 存储每个子集的长度
int ansTop;      // 当前结果集的下标
int *path;       // 存储当前路径（一个子集）
int pathTop;     // 当前路径长度

// step B# 用于 qsort 的比较函数
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// step C# 将当前 path 保存为一个子集结果
void savePathToAns() {
    int *temp = (int *)malloc(sizeof(int) * pathTop);
    for (int i = 0; i < pathTop; i++) {
        temp[i] = path[i];
    }
    ans[ansTop] = temp;
    ansLen[ansTop++] = pathTop;
}

// step D# 主体回溯函数（包含去重逻辑）
void backtracking(int *nums, int numsSize, int *used, int startIndex) {
    if (startIndex >= numsSize) return;  // step D.1# 可选终止（对子集无实际作用）

    for (int i = startIndex; i < numsSize; i++) {
        // step D.2# 剪枝逻辑：去除同一层重复选择
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;

        // step D.3# 做选择：将当前元素加入路径
        path[pathTop++] = nums[i];
        savePathToAns();

        used[i] = 1;  // 标记当前元素被选
        backtracking(nums, numsSize, used, i + 1);  // 递归下一层（下一个位置）

        // step D.4# 撤销选择
        pathTop--;
        used[i] = 0;
    }
}

// step E# 主函数：初始化并调用回溯
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // step E.1# 分配空间
    ans = (int **)malloc(sizeof(int *) * 40000);
    ansLen = (int *)malloc(sizeof(int) * 40000);
    path = (int *)malloc(sizeof(int) * 40000);
    int *used = (int *)calloc(40000, sizeof(int));  // 全 0 初始化
    ansTop = pathTop = 0;

    // step E.2# 排序数组，便于后续去重
    qsort(nums, numsSize, sizeof(int), compare);

    // step E.3# 添加空集
    savePathToAns();

    // step E.4# 启动回溯
    backtracking(nums, numsSize, used, 0);

    // step E.5# 准备返回结果
    *returnSize = ansTop;
    *returnColumnSizes = (int *)malloc(sizeof(int) * ansTop);
    for (int i = 0; i < ansTop; i++) {
        (*returnColumnSizes)[i] = ansLen[i];
    }

    return ans;
}
